package com.leecode.exercise;

/**
 * @Author: shubin_yao
 * @Date: 2022/04/04/10:39
 * @Description:
 * 栈的数组实现--java
 * 栈是先进后出的数据结构，主要有弹栈，入栈两种操作
 * 由于该栈是由数组实现的，数组的长度是固定的，当栈空间不足时，
 * 必须将原数组数据复制到一个更长的数组中，
 * 考虑到入栈时或许需要进行数组复制，平均需要复制N/2个数据项，
 * 故入栈的时间复杂度为O(N)，出栈的时间复杂度依然为O(1)
 * @author bink
 *
 */
public class Stack_Array {
    private Object[] stack;//容器
    private static final int INIT_SIZE = 2;//栈的默认大小
    private int index;//栈顶索引

    /**
     * 初始化栈_默认构造方法
     */
    public Stack_Array(){
        stack = new Object[INIT_SIZE];
        index = -1;
    }

    /**
     * 初始化栈，自定义长度
     */
    public Stack_Array(int init_size){
        if(init_size<0){
            throw new RuntimeException();
        }
        stack = new Object[init_size];
        index = -1;
    }

    /**
     * 判断栈是否为空
     * @return
     */
    public boolean isEmpty(){
        return index==-1;
    }

    /**
     * 判断是都栈满
     * @return
     */
    public boolean isFull(){
        return index>=stack.length-1;
    }

    /**
     * 入栈
     * @param obj
     */
    public synchronized void push(Object obj){
        if(isFull()){
            //动态扩容
            Object[] temp = stack;
            stack = new Object[stack.length*2];
            System.arraycopy(temp, 0, stack, 0, temp.length);
        }
        stack[++index] = obj;
    }

    /**
     * 查看栈顶元素
     * @return
     */
    public Object peek(){
        if(!isEmpty()){
            return stack[index];
        }
        return null;
    }

    /**
     * 出栈
     * @return
     */
    public synchronized Object pop(){
        if(!isEmpty()){
            Object obj = peek();
            stack[index--] = null;
            return obj;
        }
        return null;
    }

    public static void main(String[] args) {
        Stack_Array stack = new Stack_Array();
        for(int i=0;i<100;i++){
            stack.push("stack"+i);
        }
        for(int i=0;i<100;i++){
            System.out.println(stack.pop());
        }
    }
}